package queue;

/**
 * 链式队列类，实现队列接口
 *
 * @param <T>
 * @author wt
 */
public class LinkedQueue<T> implements QQueue<T> {
    private Node<T> front, rear; // front指向头结点,rear分别指队尾结点

    /**
     * 构造带头结点的空队列
     */
    public LinkedQueue() {
        front = new Node<T>(null, null);
        this.rear = this.front;
    }

    /*
     * 判断队列是否空，若空返回true
     *
     * @see queue.QQueue#isEmpty()
     */
    public boolean isEmpty() {
        if (this.front.next == null) {
            return true;
        } else {
            return false;
        }
    }

    @Override
    public T getHead() {
        if (!isEmpty()) {
            return front.next.data;
        }
        return null;
    }

    public boolean isFull() {

        return false;
    }

    /*
     * 元素x入队，空对象不能入队
     */
    public void enQueue(T x) {
        if (x == null) // 空对象不能入队
            return;
        Node<T> q = new Node<T>(x, null);
        if (this.front.next == null) { // 空队插入
            this.front.next = q;
        } else {
            this.rear.next = q; // 插入在队列之尾
        }
        this.rear = q;
    }

    /*
     * 出队，返回队头元素，若队列空返回null
     *
     * @see queue.QQueue#deQueue()
     */
    public T deQueue() {
        if (isEmpty())
            return null;
        T temp = this.front.next.data; // 取得队头元素
        this.front.next = this.front.next.next; // 删除队头结点
        if (this.front == null) {
            this.rear = null;
        }
        return temp;
    }

    /*
     * 返回队列所有元素的描述字符串，形式为“(,)”
     *
     * @see java.lang.Object#toString()
     */
    public String toString() { // 算法同不带头结点的单链表
        String str = "(";
        if (!isEmpty()) {
            for (Node<T> p = this.front.next; p != null; p = p.next) {
                str += p.data.toString();
                if (p.next != null) {
                    str += ", "; // 不是最后一个结点时后加分隔符
                }
            }
            System.out.println("当前队列:" + str + "),队列长度=" + getNodeNum());
        } else {
            System.out.println("当前队列为空...");
            return "";
        }
        return str + ")"; // 空表返回()
    }

    private int getNodeNum() {
        int num = 0;
        Node p = front.next;
        while (p != null) {
            num++;
            p = p.next;
        }
        return num;
    }
}
